package Algorithm.Tree;

/**
 * @Author cj
 * @Date 2022/6/16 21:32
 */
public class isPost {

    static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int val) {
            this.value = val;
        }
    }

    public boolean isPostArray(int[] arr) {
        if (arr == null || arr.length == 0) {
            return false;
        }
        return isPost1(arr, 0, arr.length - 1);
    }

    private boolean isPost1(int[] arr, int start, int end) {
        if (start == end) {
            return true;
        }
        int less = -1; // 左子树终点
        int more = end; // 右子树起点
        for (int i = start; i < end; i++) {
            if (arr[end] > arr[i]) {
                less = i;
            } else {
                more = more == end ? i : more;
            }
        }
        // 没有左子树或右子树
        if (less == -1 || more == end) {
            return isPost1(arr, start, end - 1);
        }
        if (less != more - 1) {
            return false;
        }
        return isPost1(arr, start, less) && isPost1(arr, more, end - 1);
    }

    // 根据后序数组构建二叉树
    public Node postArrayToBST(int[] posArr) {
        if (posArr == null) {
            return null;
        }
        return postToBST(posArr, 0, posArr.length - 1);
    }

    private Node postToBST(int[] posArr, int start, int end) {
        if (start > end) {
            return null;
        }
        Node head = new Node(posArr[end]);
        int less = -1;
        int more = end;
        for (int i = start; i < end; i++) {
            if (posArr[end] > posArr[i]) {
                less = i;
            } else {
                more = more == end ? i : more;
            }
        }
        head.left = postToBST(posArr, start, less);
        head.right = postToBST(posArr, more, end - 1);
        return head;
    }

}
